#include <basic/errcode.h>
#include <basic/tree.h>

/*================*/
/* 自顶向下伸展树 */
/*================*/
static struct splay_link *_splay_single_rotate_with_left(
        struct splay_link *K2)
{/*{{{*/
    struct splay_link *K1;

    K1=K2->left;
    K2->left=K1->right;
    K1->right=K2;

    return(K1);
}/*}}}*/

static struct splay_link *_splay_single_rotate_with_right(
        struct splay_link *K1)
{/*{{{*/
    struct splay_link *K2;

    K2=K1->right;
    K1->right=K2->left;
    K2->left=K1;

    return(K2);
}/*}}}*/

static struct splay_link *_splay(struct splay_tree *tree,
        struct splay_link *X, void *key)
{/*{{{*/
    struct splay_link *null_link=&tree->null_link;
    struct splay_link header;
    struct splay_link *left_tree_max, *right_tree_min;
    int result;

    header.left=header.right=null_link;
    left_tree_max=right_tree_min=&header;
    null_link->key=key;

    if(tree->key_type == TREE_KEY_STRING)
    {
        char *_key=(char *)key;
        while((result=strcmp(_key, (char *)X->key)) != 0)
        {
            if(result<0)
            {
                if(strcmp(_key, (char *)X->left->key) < 0)
                    X=_splay_single_rotate_with_left(X);
                if(X->left == null_link)  break;
                right_tree_min->left=X;
                right_tree_min=X;
                X=X->left; 
            }
            else
            {
                if(strcmp(_key, (char *)X->right->key) > 0)
                    X=_splay_single_rotate_with_right(X);
                if(X->right == null_link)  break;
                left_tree_max->right=X;
                left_tree_max=X;
                X=X->right; 
            }
        }
    }
    else
    {
        int _key=*(int *)key;
        while(_key != *(int *)X->key)
        {
            if(_key < *(int *)X->key)
            {
                if(_key < *(int *)X->left->key)
                    X=_splay_single_rotate_with_left(X);
                if(X->left == null_link)  break;
                right_tree_min->left=X;
                right_tree_min=X;
                X=X->left; 
            }
            else
            {
                if(_key > *(int *)X->right->key)
                    X=_splay_single_rotate_with_right(X);
                if(X->right == null_link)  break;
                left_tree_max->right=X;
                left_tree_max=X;
                X=X->right; 
            }
        }
    }

    left_tree_max->right=X->left;
    right_tree_min->left=X->right;
    X->left=header.right;
    X->right=header.left;

    return(X);
}/*}}}*/

int splay_create(unsigned int key_type, struct splay_tree *tree)
{/*{{{*/
    if(key_type != TREE_KEY_STRING && key_type != TREE_KEY_INTEGER)
        return(RET_ERR_PARA);
    if(!tree)
        return(RET_ERR_PARA);

    tree->key_type=key_type;
    tree->null_link.left=tree->null_link.right=&tree->null_link;
    tree->null_link.key=(void *)NULL;
    tree->head=&tree->null_link;
    tree->num=0;
    return(0);
}/*}}}*/

int splay_insert(struct splay_tree *tree,
        struct splay_link *insert_link)
{/*{{{*/
    int result;

    if(!tree || !insert_link)
        return(RET_ERR_PARA);

    if(tree_is_empty(tree))
    {
        insert_link->left=insert_link->right=&tree->null_link;
        tree->head=insert_link;
        tree->num++;
        return(0);
    }

    tree->head=_splay(tree, tree->head, insert_link->key);
    if(tree->key_type == TREE_KEY_STRING)
    {
        char *_key=(char *)insert_link->key;
        result=strcmp(_key, (char *)tree->head->key);
    }
    else
    {
        int _key=*(int *)insert_link->key;
        if(_key < *(int *)tree->head->key)
            result=-1;
        else
        if(_key > *(int *)tree->head->key)
            result=1;
        else
            result=0;
    }
    if(result < 0)
    {
        insert_link->left=tree->head->left;
        insert_link->right=tree->head;
        tree->head->left=&tree->null_link;
        tree->head=insert_link;
    }
    else
    if(result > 0)
    {
        insert_link->right=tree->head->right;
        insert_link->left=tree->head;
        tree->head->right=&tree->null_link;
        tree->head=insert_link;
    }
    else
        return(RET_ERR_DUPLICATE);

    tree->num++;
    return(0);
}/*}}}*/

struct splay_link *splay_delete(struct splay_tree *tree, void *key)
{/*{{{*/
    int result;
    struct splay_link *new_top_link, *delete_link;

    if(!tree || !key)
        return(NULL);

    if(tree_is_empty(tree))
        return(NULL);

    tree->head=_splay(tree, tree->head, key); 
    if(tree->key_type == TREE_KEY_STRING)
    {
        result=strcmp((char *)key,
            (char *)tree->head->key);
    }
    else
    {
        result=! (*(int *)key == *(int *)tree->head->key);
    }
    if(result != 0)  return(NULL);

    if(tree->head->left == &tree->null_link)
        new_top_link=tree->head->right;
    else
    {
        new_top_link=tree->head->left;
        new_top_link=_splay(tree, new_top_link, key);
        new_top_link->right=tree->head->right;
    }
    delete_link=tree->head;
    tree->head=new_top_link;

    tree->num--;
    return(delete_link);
}/*}}}*/

struct splay_link *splay_delete_link(struct splay_tree *tree,
    struct splay_link *delete_link)
{/*{{{*/
    return(splay_delete(tree, delete_link->key));
}/*}}}*/

struct splay_link *splay_find(struct splay_tree *tree, void *key)
{/*{{{*/
    int result;

    if(!tree || !key)
        return(NULL);

    if(tree_is_empty(tree))
        return(NULL);

    tree->head=_splay(tree, tree->head, key);
    if(tree->key_type == TREE_KEY_STRING)
    {
        result=strcmp((char *)key,
            (char *)tree->head->key);
    }
    else
    {
        result=! (*(int *)key == *(int *)tree->head->key);
    }
    if(result != 0)  return(NULL);
    else  return(tree->head);
}/*}}}*/

/*========*/
/* 红黑树 */
/*========*/
#if 0
static char _min_string[]="";
static int _min_integer=-2147483647;

static struct rb_link *_rb_single_rotate_with_left(
        struct rb_link *K2)
{/*{{{*/
    struct rb_link *K1;

    K1=K2->left;
    K2->left=K1->right;
    K1->right=K2;

    return(K1);
}/*}}}*/

static struct rb_link *_rb_single_rotate_with_right(
        struct rb_link *K1)
{/*{{{*/
    struct rb_link *K2;

    K2=K1->right;
    K1->right=K2->left;
    K2->left=K1;

    return(K2);
}/*}}}*/

static struct rb_link *_rb_rotate(struct rb_tree *tree,
        struct rb_link *P, void *key)
{/*{{{*/
    if(tree->key_type == KEY_STRING)
    {
        if(strcmp((char *)key, (char *)P->key) < 0)
        { 
            return(P->left=(strcmp((char *)key,
                (char *)P->left->key) < 0) ?
                _rb_single_rotate_with_left(P->left) :
                _rb_single_rotate_with_right(P->left));
        }
        else
        { 
            return(P->right=(strcmp((char *)key,
                (char *)P->right->key) < 0) ?
                _rb_single_rotate_with_left(P->right) :
                _rb_single_rotate_with_right(P->right));
        }
    }
    else
    {
        if(*(int *)key < *(int *)P->key)
        { 
            return(P->left=(*(int *)key <
                *(int *)P->left->key) ?
                _rb_single_rotate_with_left(P->left) :
                _rb_single_rotate_with_right(P->left));
        }
        else
        { 
            return(P->right=(*(int *)key <
                *(int *)P->right->key) ?
                _rb_single_rotate_with_left(P->right) :
                _rb_single_rotate_with_right(P->right));
        }
    }
}/*}}}*/

static void _rb_handle_reorient(struct rb_tree *tree, void *key)
{/*{{{*/
    // 反转颜色：黑->红 儿子：红->黑
    tree->X->color=RB_RED;
    tree->X->left->color=RB_BLACK;
    tree->X->right->color=RB_BLACK;

    // 父亲为红
    if(tree->P->color == RB_RED)
    {
        tree->GP->color=RB_RED;
        if((tree->key_type == KEY_STRING) ?
            (strcmp((char *)tree->X->key, (char *)tree->GP->key) !=
                strcmp((char *)tree->X->key, (char *)tree->P->key)) :
            ((*(int *)tree->X->key < *(int *)tree->GP->key) !=
                (*(int *)tree->X->key < *(int *)tree->P->key)))
                tree->P=_rb_rotate(tree, tree->GP, key);
        tree->X=_rb_rotate(tree, tree->GGP, key);
        tree->X->color=RB_BLACK;
    }
    tree->head->right->color=RB_BLACK;
}/*}}}*/

struct rb_tree *rb_init(WORD key_type)
{/*{{{*/
    struct rb_tree *tree=NULL;

    if(key_type != KEY_STRING && key_type != KEY_INTEGER)
        return(NULL);

    ALLOC_RETERR(tree, struct rb_tree, NULL);
    tree->head=tree->null=NULL;

    tree->key_type=key_type;

    ALLOC(tree->null, struct rb_link, ERROR_OUT);
    tree->null->color=RB_BLACK;
    tree->null->left=tree->null->right=tree->null;

    ALLOC(tree->head, struct rb_link, ERROR_OUT);
    tree->head->color=RB_BLACK;
    tree->head->left=tree->head->right=tree->null;
    tree->head->key=(key_type == KEY_STRING) ?
        (void *)_min_string : 
        (void *)&_min_integer;

    return(tree);

ERROR_OUT:
    FREE(tree->null);
    FREE(tree->head);
    FREE(tree);
    return(NULL);
}/*}}}*/

int rb_insert(struct rb_tree *tree, struct rb_link *I)
{/*{{{*/
    int result;

    tree->X=tree->P=tree->GP=tree->head;
    tree->null->key=I->key;
    while((result=(tree->key_type == KEY_STRING) ?
        strcmp((char *)I->key, (char *)tree->X->key) :
        *(int *)I->key - *(int *)tree->X->key) != 0)
    {
        tree->GGP=tree->GP;
        tree->GP=tree->P;
        tree->P=tree->X;
        if(result < 0)
            tree->X=tree->X->left;
        else
            tree->X=tree->X->right;
        if(tree->X->left->color == RB_RED &&
            tree->X->right->color == RB_RED)
            _rb_handle_reorient(tree, I->key);
    }
    if(tree->X != tree->null)
        return(-1); // 重复

    I->left=I->right=tree->null;
    if((tree->key_type == KEY_STRING) ?
        strcmp((char *)I->key, (char *)tree->P->key) < 0 :
        *(int *)I->key != *(int *)tree->P->key)
        tree->P->left=I;
    else
        tree->P->right=I;
    _rb_handle_reorient(tree, I->key);

    return(0);
}/*}}}*/

struct rb_link *rb_delete(struct rb_tree *tree, void *key)
{/*{{{*/
    return(NULL);
}/*}}}*/

struct rb_link *rb_delete_by_link(struct rb_tree *tree,
    struct rb_link *D)
{/*{{{*/
    return(rb_delete(tree, D->key));
}/*}}}*/

struct rb_link *rb_find(struct rb_tree *tree, void *key)
{/*{{{*/
    struct rb_link *X;
    int result;

    X=tree->head;
    tree->null->key=key;
    while((result=(tree->key_type == KEY_STRING) ?
        strcmp((char *)key, (char *)X->key) :
        *(int *)key - *(int *)X->key) != 0)
    {
        if(result < 0)
            tree->X=tree->X->left;
        else
            tree->X=tree->X->right;
    }
    if(X == tree->null)
        return(NULL);

    return(X);
}/*}}}*/
#endif

static void _rb_rotate_left(struct rb_tree *tree, struct rb_link *X)
{/*{{{*/
    struct rb_link *NULL_LINK=&tree->null_link;
    struct rb_link *R=X->right;

    if((X->right=R->left) != NULL_LINK)
        R->left->parent=X;
    R->left=X;

    if((R->parent=X->parent) != NULL_LINK)
        if (X == X->parent->left)
            X->parent->left=R;
        else
            X->parent->right=R;
    else
        tree->head=R;
    X->parent=R;
}/*}}}*/

static void _rb_rotate_right(struct rb_tree *tree, struct rb_link *X)
{/*{{{*/
    struct rb_link *NULL_LINK=&tree->null_link;
    struct rb_link *L=X->left;

    if((X->left=L->right) != NULL_LINK)
        L->right->parent=X;
    L->right=X;

    if((L->parent=X->parent) != NULL_LINK)
        if(X == X->parent->right)
            X->parent->right=L;
        else
            X->parent->left=L;
    else
        tree->head=L;
    X->parent=L;
}/*}}}*/

int rb_create(unsigned int key_type, struct rb_tree *tree)
{/*{{{*/
    if(key_type != TREE_KEY_STRING && key_type != TREE_KEY_INTEGER)
        return(RET_ERR_PARA);
    if(!tree)
        return(RET_ERR_PARA);

    tree->key_type=key_type;
    tree->null_link.color=RB_BLACK;
    tree->null_link.left=tree->null_link.right=&tree->null_link;
    tree->null_link.parent=&tree->null_link;
    tree->null_link.key=(void *)NULL;
    tree->head=&tree->null_link;
    tree->num=0;
    return(0);
}/*}}}*/

int rb_insert(struct rb_tree *tree, struct rb_link *I)
{/*{{{*/
    struct rb_link *NULL_LINK;
    struct rb_link *X, *P, *U, *GP;
    int result;

    if(!tree || !I)
        return(RET_ERR_PARA);

    NULL_LINK=&tree->null_link;

    // 查找位置
    X=tree->head;
    P=NULL_LINK;
    if(tree->key_type == TREE_KEY_STRING)
    {
        while(X != NULL_LINK)
        {
            result=strcmp((char *)I->key, (char *)X->key);
            if(result == 0)  return(RET_ERR_DUPLICATE);    // 重复
            P=X;
            X=(result < 0) ? X->left : X->right;
        }
    }
    else
    {
        while(X != NULL_LINK)
        {
            result=*(int *)I->key - *(int *)X->key;
            if(result == 0)  return(RET_ERR_DUPLICATE);    // 重复
            P=X;
            X=(result < 0) ? X->left : X->right;
        }
    }

    // 插入
    I->parent=P;
    I->left=I->right=NULL_LINK;
    I->color=RB_RED;
    if(P != NULL_LINK)
    {
        result=(tree->key_type == TREE_KEY_STRING) ?
            strcmp((char *)I->key, (char *)P->key) :
            (*(int *)I->key - *(int *)P->key);
        if(result < 0)
            P->left=I;
        else
            P->right=I;
    }
    else
        tree->head=I;

    // 检查红黑属性
    X=I;
    while(X != tree->head && X->parent->color == RB_RED)
    {
        // 违例
        P=X->parent;
        GP=P->parent;
        if(P == GP->left)
        {
            U=GP->right;
            if(U->color == RB_RED)  // 舅舅为红
            {
                P->color=RB_BLACK;
                U->color=RB_BLACK;
                GP->color=RB_RED;
                X=GP;
            }
            else // 舅舅为黑或不存在
            {
                if(X == P->right)
                {
                    X=P;
                    _rb_rotate_left(tree, X);
                    P=X->parent;
                    GP=P->parent;
                }
                // 改变颜色并P,GP右旋
                P->color=RB_BLACK;
                GP->color=RB_RED;
                _rb_rotate_right(tree, GP);
            }
        }
        else    // 镜像
        {
            U=GP->left;
            if(U->color == RB_RED)    // 舅舅为红
            {
                U->color=RB_BLACK;
                P->color=RB_BLACK;
                GP->color=RB_RED;
                X=GP;
            }
            else    // 舅舅为黑或不存在
            {
                if(X == P->left)
                {
                    X=P;
                    _rb_rotate_right(tree, X);
                    P=X->parent;
                    GP=P->parent;
                }
                // 改变颜色并P,GP左旋
                P->color=RB_BLACK;
                GP->color=RB_RED;
                _rb_rotate_left(tree, GP);
            }
        }
    }
    tree->head->color=RB_BLACK;

    tree->num++;
    return(0);
}/*}}}*/

struct rb_link *rb_delete(struct rb_tree *tree, void *key)
{/*{{{*/
    struct rb_link *D;

    if((D=rb_find(tree, key)))
        if(rb_delete_link(tree, D))
            return(D);
    return(NULL);
}/*}}}*/

struct rb_link *rb_delete_link(struct rb_tree *tree,
        struct rb_link *D)
{/*{{{*/
    struct rb_link *NULL_LINK;
    struct rb_link *X, *P, *C;
    struct rb_link *W;
    unsigned int X_color;

    if(!tree || !D)
        return(NULL);

    NULL_LINK=&tree->null_link;
    if(D->left == NULL_LINK || D->right == NULL_LINK)
    {
        // 至少有一个儿子为空
        X=D;  
    }
    else
    {    
        // 右子树向左下溯至儿子为空的节点
        X=D->right;
        while(X->left != NULL_LINK)
            X=X->left;
    }       

    // 将X删去
    P=X->parent;
    X_color=X->color;
    if(X->left != NULL_LINK)
        C=X->left;
    else            
        C=X->right;
    if(C != NULL_LINK)
        C->parent=P;
    if(P != NULL_LINK)
        if(X == P->left)
            P->left=C; 
        else    
            P->right=C;
    else    
        tree->head=C;

    if(X != D)  // D左右子树都不为空
    {
        if(X->parent == D)  // D是要被删除的，C的父亲应改成X
            P=X;
        X->color=D->color;
        X->left=D->left;
        X->right=D->right;
        X->parent=D->parent;
        if(D->parent != NULL_LINK)
            if(D->parent->left == D)
                D->parent->left=X;
            else
                D->parent->right=X;
        else
            tree->head=X;
        D->left->parent=X;
        if(D->right != NULL_LINK)
            D->right->parent=X;
    }
    if(X_color == RB_RED)
    {
        tree->num--;
        return(D);
    }

    // 删除节点为黑，调整树
    while(C != tree->head && C->color == RB_BLACK)
    {
        if(C == P->left)
        {
            W=P->right;
            if(W->color == RB_RED)
            {
                W->color=RB_BLACK;
                P->color=RB_RED;
                _rb_rotate_left(tree, P);
                W=P->right;
            }
            if(W->left->color == RB_BLACK &&
                    W->right->color == RB_BLACK)
            {
                W->color=RB_RED;
                C=P;
                P=C->parent;
            }
            else
            {
                if(W->right->color == RB_BLACK)
                {
                    W->left->color=RB_BLACK;
                    W->color=RB_RED;
                    _rb_rotate_right(tree, W);
                    W=P->right;
                }
                W->color=P->color;
                P->color=RB_BLACK;
                W->right->color=RB_BLACK;
                _rb_rotate_left(tree, P);
                C=tree->head;
            }
        }
        else
        {
            W=P->left;
            if(W->color == RB_RED)
            {
                W->color=RB_BLACK;
                P->color=RB_RED;
                _rb_rotate_right(tree, P);
                W=P->left;
            }
            if(W->left->color == RB_BLACK &&
                    W->right->color == RB_BLACK)
            {
                W->color=RB_RED;
                C=P;
                P=C->parent;
            }
            else
            {
                if(W->left->color == RB_BLACK)
                {
                    W->right->color=RB_BLACK;
                    W->color=RB_RED;
                    _rb_rotate_left(tree, W);
                    W=P->left;
                }
                W->color=P->color;
                P->color=RB_BLACK;
                W->left->color=RB_BLACK;
                _rb_rotate_right(tree, P);
                C=tree->head;
            }
        }
    }
    C->color=RB_BLACK; 

    tree->num--;
    return(D);
}/*}}}*/

struct rb_link *rb_find(struct rb_tree *tree, void *key) 
{/*{{{*/
    struct rb_link *NULL_LINK;
    struct rb_link *C;
    int result;

    if(!tree || !key)
        return(NULL);

    NULL_LINK=&tree->null_link;
    C=tree->head;
    if(tree->key_type == TREE_KEY_STRING)
    {
        while(C != NULL_LINK)
        {
            result=strcmp((char *)key, (char *)C->key);
            if(result == 0)
                return(C);
            if(result < 0)
                C=C->left;
            else
                C=C->right;
        }
    }
    else
    {
        while(C != NULL_LINK)
        {
            result=*(int *)key - *(int *)C->key;
            if(result == 0)
                return(C);
            if(result < 0)
                C=C->left;
            else
                C=C->right;
        }
    }
    return(NULL);
}/*}}}*/
